【⭐】CF 2121F

先分解成两个问题分别考虑。

对于加和问题，前缀和是显然的，如何进一步优化？

对于最大值问题，运用最大值摆在摆在名字里的性质，转化为子序列至少有一个值等于 $t$ 的元素且不存在值大于 $t$ 的元素。另外还有一种转化方法是子序列最大值不大于 $t$ 的个数减去子序列最大值不大于 $t-1$ 的个数。

问题一：给定一列数 $a_1,a_2,\cdots ,a_n$，如何求出有多少个连续子序列 $a_l,a_{l+1},\cdots ,a_r$ 满足子序列之和为 $s$?

答案：自然而然会先想到维护一个前缀和 $P$，但简单使用前缀和复杂度仍然为 $\mathcal{O}(n^2)$，无法接受。考虑变形 $P_r-P_{l-1}=s$ 得到 $P_r-s=P_{l-1}$，因此遍历同时维护一个 map 记录 $P_l$ 的值与端点数，这样就可以通过枚举右端点 $r$ 从而在 $\mathcal{O}(n\log n)$ 的时间复杂度内求出。

问题二：给定一列数 $a_1,a_2,\cdots ,a_n$，如何求出有多少个连续子序列 $a_l,a_{l+1},\cdots ,a_r$ 满足子序列最大值为 $t$?

该问题的做法比较多，此处仅举两例：

1. 将条件转化为子序列至少有一个值等于 $t$ 的元素且不存在值大于 $t$ 的元素。将序列中所有大于 $t$ 的元素视作分隔符，分割后在多个互不相交的子序列中处理。在这些子序列中，可以记录所有值为 $t$ 的元素的位置，枚举右端点（枚举左端点同理），左端点的最大值（子序列长度的最小值）即为离右端点左侧最近的一个 $t$ 的位置。另外注意到前缀最大值是弱递增的，也考虑 ST 表预处理子序列最大值，随后枚举左端点，二分满足序列最大值为 $t$ 的右端点的最大与最小值，二者相减即为固定左端点时的序列数。两个方法殊途同归。
2. 将条件转化为最大值不大于 $t$ 的连续子序列个数减去最大值不大于 $t-1$ 的连续子序列个数。同样将序列中所有大于 $t$ 的元素视作分隔符，分割后在多个互不相交的子序列中处理。对每一个子序列，记其长度为 $l_i$，则共有 ${\displaystyle \frac{l_i(l_i+1)}{2}}$ 个最大值不大于 $t$ 的子序列。随后，如法炮制计算出最大值不大于 $t-1$ 的子序列个数，二者相减得到答案。

顺带一提，对这两个问题给出的做法都十分常见，可以考虑单独记忆。

回到正题，我们考虑如何将这两个问题综合到一起考虑。我们可以一边进行问题一中遍历右端点的过程，与此同时加上最大值的限制，我们考虑使用上面给出的方法一。具体实现方法为：

维护一个双指针 $l$ 与 $r$，目的是使得 $\underset{i=l}{\overset{r}{max}}{a}_i=t$。右指针不停移动，

• 如果 $a_r>t$，直接清空记录序列和的 map，并令 $l,r\leftarrow r+1$ 重新计算。
• 如果 $a_r=t$，认为最大值条件已经得到满足，此时才将所有的 $P_{l-1},P_l,\cdots ,P_{r-1}$ 加入 map 考察求和条件是否满足。加入完成后令 $l\leftarrow r+1$，避免将重复的 $P_l$ 加入 map。
• 如果 $a_r<t$，认为最大值条件没有得到满足，什么都不做。

这样我们就能在先限定最大值条件得到满足的条件下考察序列和是否满足，时间复杂度为 $\mathcal{O}(n\log n)$。

注：本题存在特意构造了哈希冲突的数据点，所以请不要使用 unordered_map，会 TLE on test 32。